Community detection thresholds and the weak Ramanujan property,” Nov. 2013, available at: http://arxiv.org/abs/1311.3085

Decelle et al. [1] conjectured the existence of a sharp thresh-old on model parameters for community detection in sparse random graphs drawn from the stochastic block model. Mos-sel, Neeman and Sly [2] established the negative part of the conjecture, proving impossibility of non-trivial reconstruc-tion below the threshold. In this work we solve the positive part of the conjecture. To that end we introduce a mod-ified adjacency matrix B which counts self-avoiding paths of a given length ℓ between pairs of nodes. We then prove that for logarithmic length ℓ, the leading eigenvectors of this modified matrix provide a non-trivial reconstruction of the underlying structure, thereby settling the conjecture. A key step in the proof consists in establishing a weak Ramanujan property of the constructed matrix B. Namely, the spectrum of B consists in two leading eigenvalues ρ(B), λ2 and n − 2 eigenvalues of a lower order O(nǫ ρ(B)) for all ǫ> 0, ρ(B) denoting B’s spectral radius